class Solution {
    public:
        int n,m;
        vector<int> getMaxMatrix(vector<vector<int>>& matrix) {
            n = matrix.size();
            m = matrix[0].size();
            
            vector<vector<int>> sum(n + 10,vector<int>(m + 10));
            vector<vector<int>> arr(n + 10,vector<int>(m + 10));
    
            for(int i = 0; i < n; i ++)
            {
                for(int j = 0; j < m; j ++)
                {
                    arr[i + 1][j + 1] = matrix[i][j];
                }
            }
            for(int i = 1; i <= n; i ++)
            {
                for(int j = 1; j <= m; j ++)
                {
                    sum[i][j] = sum[i][j - 1] + arr[i][j];
                }
            }
            int ans = -0x3f3f3f3f;
            vector<int> op (4);
            vector<int>f(n + 10);
            for(int i = 1; i <= m; i ++){
                for(int j = i; j <= m; j ++)
                {
                    vector<int>rec(n + 10);
                    rec[1] = 1;
                    for(int k = 1; k <= n; k++)
                    {
                        f[k] = sum[k][j] - sum[k][i - 1];
                    }
                    for(int k = 1; k <= n; k ++)
                    {
                        f[k] = max(f[k],f[k] + f[k - 1]);
                        if(f[k - 1] <= 0) rec[k] = k;
                        else rec[k] = rec[k - 1];
                    }
                    
                    for(int k = 1; k <= n; k ++)
                    {
                        if(f[k] > ans)
                        {
                            ans = f[k];
                            op[0] = rec[k] - 1;
                            op[1] = i - 1;
                            op[2] = k - 1;
                            op[3] = j - 1;
                        }
                    }
                }
            }
            return op;
        }
    
    };